package history.study.tow_pointer;

public class LeetCode_74 {

    public static void main(String[] args) {
        int test[][] = {{1,3,5,7},{10,11,16,20},{23,30,34,60}};
        System.out.println(searchMatrix(test,13));
    }

    // 1. 从上往下，对每一行的第一列进行二分查找
    // 2. 定位到目标行后，从左往右，进行二分查找
    public static boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length<=0||matrix[0].length<=0) return false;

        int arrayLength = matrix[0].length-1;
        int left = 0;
        int right = matrix.length-1;
        int mid =(left+right)/2;
        // 定位目标数字所在的行
        while (left <= right) {
            mid = (left+right)/2;
            if (matrix[mid][0]== target||matrix[mid][arrayLength] == target) return true;
            if (matrix[mid][0] > target) {
                right = mid-1;
            } else if (matrix[mid][arrayLength] < target) {
                left = mid+1;
            } else {
                break;
            }
        }

        // 定位目标数字所在列
        int targetRow = mid;
        left = 0;
        right = arrayLength;
        while (left <= right) {
            mid = (left+right)/2;
            if (matrix[targetRow][mid] == target) return true;
            if (matrix[targetRow][mid] > target) {
                right = mid-1;
            } else {
                left = mid+1;
            }
        }
        return false;
    }
}
